// Copyright (c) Meta Platforms, Inc. and affiliates.

#ifndef ZSTRONG_COMMON_DETAIL_TABLE_H
#define ZSTRONG_COMMON_DETAIL_TABLE_H

#include <limits.h>
#include <string.h>
#include "openzl/common/allocation.h"
#include "openzl/common/assertion.h"
#include "openzl/shared/bits.h"
#include "openzl/shared/overflow.h"
#include "openzl/shared/portability.h"
#include "openzl/shared/utils.h"
#include "openzl/shared/xxhash.h"

ZL_BEGIN_C_DECLS

/**
 * The table is implemented through a type erased GenericTable implementation.
 * This gets wrapped by the type-safe API generated by macros for each table.
 * The macros generate a static constant GenericTable_Policy that configures the
 * GenericTable for its types and hash/equality functions.
 *
 * All of the GenericTable functions are "templated" on the constant policy, and
 * are meant to be inlined so that they can do constant propagation on the
 * policy.
 *
 * The GenericTable is implemented via separate chaining, but with the first
 * element in the chain inlined into the table. This allows fast operations when
 * the load factor is low, and collisions are rare. This is a tradeoff of memory
 * for simplicity and speed, since this table runs with a load factor of 0.5.
 * Later down the line we can re-evaluate this tradeoff, and see if we want to
 * change the implementation.
 */

// Attribute for all table functions in the public API
#define ZL_TABLE_INLINE ZL_INLINE
// Attribute to force inline "templated" functions
#define ZL_TABLE_FORCE_INLINE ZL_FORCE_INLINE
// Attributes to force functions to be outlined.
// This is used for cold functions, like rehashing, in hot loops.
#define ZL_TABLE_NO_INLINE ZL_FORCE_NOINLINE

// Portable memcmp that uses compiler intrinsics when available for better
// performance
#if defined(__GNUC__) || defined(__clang__)
#    define ZL_TABLE_MEMCMP __builtin_memcmp
#else
#    define ZL_TABLE_MEMCMP memcmp
#endif

/// Make Table_-typed tables call a default (XXH3-backed) hash function.
#define ZL_DECLARE_TABLE_DEFAULT_HASH_FN(Table_, Key_)                 \
    ZL_TABLE_FORCE_INLINE size_t Table_##_genericHash(void const* key) \
    {                                                                  \
        return XXH3_64bits(key, sizeof(Key_));                         \
    }

/// Make Table_-typed tables call the Key_ type's predefined hash function.
#define ZL_DECLARE_TABLE_PREDEF_HASH_FN(Table_, Key_)                  \
    ZL_TABLE_FORCE_INLINE size_t Table_##_genericHash(void const* key) \
    {                                                                  \
        return Key_##_hash((Key_ const*)key);                          \
    }

/// Make Table_-typed tables call a user-defined hash function.
#define ZL_DECLARE_TABLE_CUSTOM_HASH_FN(Table_, Key_)                  \
    ZL_TABLE_FORCE_INLINE size_t Table_##_genericHash(void const* key) \
    {                                                                  \
        return Table_##_hash((Key_ const*)key);                        \
    }

/// Make Table_-typed tables call a default (memcmp()-backed) equality function.
#define ZL_DECLARE_TABLE_DEFAULT_EQ_FN(Table_, Key_)         \
    ZL_TABLE_FORCE_INLINE bool Table_##_genericEq(           \
            void const* lhs, void const* rhs)                \
    {                                                        \
        return ZL_TABLE_MEMCMP(lhs, rhs, sizeof(Key_)) == 0; \
    }

/// Make Table_-typed tables call the Key_ type's predefined equality function.
#define ZL_DECLARE_TABLE_PREDEF_EQ_FN(Table_, Key_)           \
    ZL_TABLE_FORCE_INLINE bool Table_##_genericEq(            \
            void const* lhs, void const* rhs)                 \
    {                                                         \
        return Key_##_eq((Key_ const*)lhs, (Key_ const*)rhs); \
    }

/// Make Table_-typed tables call a user-defined equality function.
#define ZL_DECLARE_TABLE_CUSTOM_EQ_FN(Table_, Key_)             \
    ZL_TABLE_FORCE_INLINE bool Table_##_genericEq(              \
            void const* lhs, void const* rhs)                   \
    {                                                           \
        return Table_##_eq((Key_ const*)lhs, (Key_ const*)rhs); \
    }

#define ZL_DECLARE_TABLE(Table_, Entry_, Key_, kPolicy_)                       \
    typedef struct {                                                           \
        GenericTable table_;                                                   \
    } Table_;                                                                  \
                                                                               \
    typedef struct {                                                           \
        GenericTable_Iter iter_;                                               \
    } Table_##_Iter;                                                           \
                                                                               \
    typedef struct {                                                           \
        GenericTable_Iter iter_;                                               \
    } Table_##_IterMut;                                                        \
                                                                               \
    typedef struct {                                                           \
        Entry_* ptr;                                                           \
        bool inserted;                                                         \
        bool badAlloc;                                                         \
    } Table_##_Insert;                                                         \
                                                                               \
    ZL_DECLARE_TABLE_DETAILS(Table_, Entry_, Key_, kPolicy_)                   \
                                                                               \
    ZL_TABLE_INLINE Table_ Table_##_create(uint32_t maxCapacity)               \
    {                                                                          \
        return (Table_){ GenericTable_create(NULL, maxCapacity) };             \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_ Table_##_createInArena(                             \
            Arena* arena, uint32_t maxCapacity)                                \
    {                                                                          \
        return (Table_){ GenericTable_create(arena, maxCapacity) };            \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE void Table_##_destroy(Table_* table)                       \
    {                                                                          \
        GenericTable_destroy(&table->table_);                                  \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE void Table_##_clear(Table_* table)                         \
    {                                                                          \
        GenericTable_clear(&table->table_, kPolicy_);                          \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE size_t Table_##_size(Table_ const* table)                  \
    {                                                                          \
        return GenericTable_size(&table->table_);                              \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE size_t Table_##_capacity(Table_ const* table)              \
    {                                                                          \
        return GenericTable_capacity(&table->table_);                          \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE size_t Table_##_maxCapacity(Table_ const* table)           \
    {                                                                          \
        return GenericTable_maxCapacity(&table->table_);                       \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE bool Table_##_reserve(                                     \
            Table_* table, uint32_t capacity, bool guaranteeNoAllocations)     \
    {                                                                          \
        return GenericTable_reserve(                                           \
                &table->table_, capacity, guaranteeNoAllocations, kPolicy_);   \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_ const* Table_##_find(                               \
            Table_ const* table, Key_ const* key)                              \
    {                                                                          \
        return (Entry_ const*)GenericTable_find(                               \
                &table->table_, key, kPolicy_);                                \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_* Table_##_findMut(Table_* table, Key_ const* key)   \
    {                                                                          \
        return (Entry_*)GenericTable_find(&table->table_, key, kPolicy_);      \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_ const* Table_##_findVal(                            \
            Table_ const* table, Key_ const key)                               \
    {                                                                          \
        return (Entry_ const*)GenericTable_find(                               \
                &table->table_, &key, kPolicy_);                               \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_* Table_##_findMutVal(Table_* table, Key_ const key) \
    {                                                                          \
        return (Entry_*)GenericTable_find(&table->table_, &key, kPolicy_);     \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE bool Table_##_contains(                                    \
            Table_ const* table, Key_ const* key)                              \
    {                                                                          \
        return GenericTable_find(&table->table_, key, kPolicy_) != NULL;       \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE bool Table_##_containsVal(                                 \
            Table_ const* table, Key_ const key)                               \
    {                                                                          \
        return GenericTable_find(&table->table_, &key, kPolicy_) != NULL;      \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_##_Insert Table_##_insert(                           \
            Table_* table, Entry_ const* entry)                                \
    {                                                                          \
        GenericTable_Insert insert = GenericTable_insert(                      \
                &table->table_, entry, kPolicy_, Detail_##Table_##_reserve);   \
        return (Table_##_Insert){ (Entry_*)insert.ptr,                         \
                                  insert.inserted,                             \
                                  insert.badAlloc };                           \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_##_Insert Table_##_insertVal(                        \
            Table_* table, Entry_ const entry)                                 \
    {                                                                          \
        GenericTable_Insert insert = GenericTable_insert(                      \
                &table->table_, &entry, kPolicy_, Detail_##Table_##_reserve);  \
        return (Table_##_Insert){ (Entry_*)insert.ptr,                         \
                                  insert.inserted,                             \
                                  insert.badAlloc };                           \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE bool Table_##_erase(Table_* table, Key_ const* key)        \
    {                                                                          \
        return GenericTable_erase(&table->table_, key, kPolicy_);              \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE bool Table_##_eraseVal(Table_* table, Key_ const key)      \
    {                                                                          \
        return GenericTable_erase(&table->table_, &key, kPolicy_);             \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_##_Iter Table_##_iter(Table_ const* table)           \
    {                                                                          \
        return (Table_##_Iter){ GenericTable_iter(&table->table_, kPolicy_) }; \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_##_IterMut Table_##_iterMut(Table_* table)           \
    {                                                                          \
        return (Table_##_IterMut){ GenericTable_iter(                          \
                &table->table_, kPolicy_) };                                   \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_ const* Table_##_Iter_next(Table_##_Iter* iter)      \
    {                                                                          \
        return (Entry_ const*)GenericTable_Iter_next(&iter->iter_, kPolicy_);  \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_* Table_##_IterMut_next(Table_##_IterMut* iter)      \
    {                                                                          \
        return (Entry_*)GenericTable_Iter_next(&iter->iter_, kPolicy_);        \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_ const* Table_##_Iter_get(Table_##_Iter iter)        \
    {                                                                          \
        return (Entry_ const*)GenericTable_Iter_get(iter.iter_);               \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Entry_* Table_##_IterMut_get(Table_##_IterMut iter)        \
    {                                                                          \
        return (Entry_*)GenericTable_Iter_get(iter.iter_);                     \
    }                                                                          \
                                                                               \
    ZL_TABLE_INLINE Table_##_Iter Table_##_IterMut_const(                      \
            Table_##_IterMut iter)                                             \
    {                                                                          \
        return (Table_##_Iter){ iter.iter_ };                                  \
    }                                                                          \
                                                                               \
    struct Detail_##Table_##_NeedsTrailingSemicolon_ {                         \
        int x;                                                                 \
    }

#define ZL_DECLARE_TABLE_DETAILS(Table_, Entry_, Key_, kPolicy_) \
    ZL_TABLE_NO_INLINE bool Detail_##Table_##_reserve(           \
            GenericTable* table, uint32_t capacity)              \
    {                                                            \
        return GenericTable_reserve(                             \
                table,                                           \
                capacity,                                        \
                /* guaranteeNoAllocations */ false,              \
                kPolicy_);                                       \
    }

#define ZL_DECLARE_TABLE_POLICY(kPolicy_, Table_, Entry_, HashFn_, EqFn_) \
    typedef struct {                                                      \
        Entry_ entry;                                                     \
        uint32_t next;                                                    \
    } Detail_##Table_##_Bucket;                                           \
                                                                          \
    static GenericTable_Policy const kPolicy_ = {                         \
        .hashFn      = HashFn_,                                           \
        .eqFn        = EqFn_,                                             \
        .kBucketSize = sizeof(Detail_##Table_##_Bucket),                  \
        .kEntrySize  = sizeof(Entry_),                                    \
        .kNextOffset = offsetof(Detail_##Table_##_Bucket, next),          \
    }

#define ZL_DECLARE_TABLE_DEFAULT_POLICY(Table_) \
    ZL_DECLARE_TABLE_POLICY(                    \
            Detail_##Table_##_kPolicy,          \
            Table_,                             \
            Table_##_Entry,                     \
            Table_##_genericHash,               \
            Table_##_genericEq)

typedef struct {
    size_t (*hashFn)(void const*);
    bool (*eqFn)(void const*, void const*);
    size_t kBucketSize;
    size_t kEntrySize;
    size_t kNextOffset;
} GenericTable_Policy;

#define ZL_TABLE_MAX_CAPACITY ((1u << 30) - 1)
#define ZL_TABLE_LOAD_FACTOR 2

typedef struct {
    uint8_t* table;
    uint8_t* chain;
    uint32_t tableMask;
    uint32_t tableSize;
    uint32_t tableCapacity;
    uint32_t chainSize;
    uint32_t chainCapacity;
    uint32_t chainFreeList;
    uint32_t maxCapacity;
    Arena* arena;
} GenericTable;

typedef struct {
    void* ptr;
    bool inserted;
    bool badAlloc;
} GenericTable_Insert;

typedef struct {
    GenericTable const* table;
    void* bucket;
    uint32_t index;
} GenericTable_Iter;

typedef bool (*GenericTable_OutlinedReserve)(GenericTable*, uint32_t);

#define ZL_TABLE_NEXT_BUCKET_EMPTY ((uint32_t)-1)
#define ZL_TABLE_NEXT_CHAIN_EMPTY ((uint32_t)-2)

ZL_TABLE_INLINE uint8_t*
GenericTable_reallocMem(GenericTable* table, uint8_t* ptr, size_t newSize)
{
    if (table->arena != NULL) {
        return (uint8_t*)ALLOC_Arena_realloc(table->arena, ptr, newSize);
    } else {
        return (uint8_t*)ZL_realloc(ptr, newSize);
    }
}

ZL_TABLE_INLINE void GenericTable_freeMem(GenericTable* table, uint8_t* ptr)
{
    if (table->arena != NULL) {
        ALLOC_Arena_free(table->arena, ptr);
    } else {
        ZL_free(ptr);
    }
}

ZL_TABLE_INLINE void
GenericTable_init(GenericTable* table, Arena* arena, uint32_t maxCapacity)
{
    memset(table, 0, sizeof(*table));
    table->chainFreeList = ZL_TABLE_NEXT_CHAIN_EMPTY;
    // tableMask == 0 is a special case that means the table is empty.
    table->tableMask = 0;
    ZL_ASSERT_LE(maxCapacity, ZL_TABLE_MAX_CAPACITY);
    table->maxCapacity = ZL_MIN(maxCapacity, ZL_TABLE_MAX_CAPACITY);
    table->arena       = arena;
}

ZL_TABLE_INLINE GenericTable
GenericTable_create(Arena* arena, uint32_t maxCapacity)
{
    GenericTable table;
    GenericTable_init(&table, arena, maxCapacity);
    return table;
}

ZL_TABLE_INLINE void GenericTable_destroy(GenericTable* table)
{
    GenericTable_freeMem(table, table->table);
    GenericTable_freeMem(table, table->chain);
    memset(table, 0, sizeof(*table));
}

ZL_TABLE_INLINE size_t GenericTable_capacity(GenericTable const* table)
{
    return table->tableCapacity;
}

ZL_TABLE_INLINE size_t GenericTable_maxCapacity(GenericTable const* table)
{
    return table->maxCapacity;
}

ZL_TABLE_INLINE size_t GenericTable_size(GenericTable const* table)
{
    return table->tableSize;
}

ZL_TABLE_FORCE_INLINE void* GenericTable_getTableBucket(
        GenericTable const* table,
        void const* key,
        GenericTable_Policy const kPolicy)
{
    ZL_ASSERT_NE(table->tableMask, 0);
    size_t const hash = kPolicy.hashFn(key);
    size_t const idx  = hash & table->tableMask;
    return (uint8_t*)table->table + idx * kPolicy.kBucketSize;
}

ZL_TABLE_FORCE_INLINE void* GenericTable_getChainBucket(
        GenericTable const* table,
        size_t idx,
        GenericTable_Policy const kPolicy)
{
    ZL_ASSERT_LE(idx, table->chainSize);
    return (uint8_t*)table->chain + idx * kPolicy.kBucketSize;
}

ZL_TABLE_FORCE_INLINE uint32_t* GenericTable_Bucket_next(
        void* bucket,
        GenericTable_Policy const kPolicy)
{
    void* next = (uint8_t*)bucket + kPolicy.kNextOffset;
    return (uint32_t*)next;
}

ZL_TABLE_INLINE void GenericTable_Iter_skipToNonEmptyBucket(
        GenericTable_Iter* iter,
        GenericTable_Policy const kPolicy)
{
    if (iter->bucket == NULL) {
        return;
    }
    uint32_t next = *GenericTable_Bucket_next(iter->bucket, kPolicy);
    while (next == ZL_TABLE_NEXT_BUCKET_EMPTY) {
        ZL_ASSERT_NE(iter->table->tableMask, 0);
        if (iter->index == iter->table->tableMask) {
            iter->bucket = NULL;
            return;
        }
        ++iter->index;
        iter->bucket = iter->table->table + iter->index * kPolicy.kBucketSize;
        next         = *GenericTable_Bucket_next(iter->bucket, kPolicy);
    }
}

ZL_TABLE_INLINE GenericTable_Iter
GenericTable_iter(GenericTable const* table, GenericTable_Policy const kPolicy)
{
    GenericTable_Iter iter = { table, table->table, 0 };
    GenericTable_Iter_skipToNonEmptyBucket(&iter, kPolicy);
    return iter;
}

ZL_TABLE_FORCE_INLINE void* GenericTable_Iter_get(GenericTable_Iter iter)
{
    return iter.bucket;
}

ZL_TABLE_INLINE void* GenericTable_Iter_next(
        GenericTable_Iter* iter,
        GenericTable_Policy const kPolicy)
{
    if (iter->bucket == NULL) {
        return NULL;
    }
    void* const result = iter->bucket;

    uint32_t next = *GenericTable_Bucket_next(iter->bucket, kPolicy);
    ZL_ASSERT_NE(next, ZL_TABLE_NEXT_BUCKET_EMPTY);
    if (next != ZL_TABLE_NEXT_CHAIN_EMPTY) {
        iter->bucket = GenericTable_getChainBucket(iter->table, next, kPolicy);
        return result;
    }

    ZL_ASSERT_NE(iter->table->tableMask, 0);
    if (iter->index == iter->table->tableMask) {
        iter->bucket = NULL;
        return result;
    }
    ++iter->index;
    iter->bucket = iter->table->table + iter->index * kPolicy.kBucketSize;
    GenericTable_Iter_skipToNonEmptyBucket(iter, kPolicy);

    return result;
}

ZL_TABLE_FORCE_INLINE void* GenericTable_find(
        GenericTable const* table,
        void const* key,
        GenericTable_Policy const kPolicy)
{
    ZL_ASSERT_NN(key);
    if (table->table == NULL) {
        return NULL;
    }

    void* bucket  = GenericTable_getTableBucket(table, key, kPolicy);
    uint32_t next = *GenericTable_Bucket_next(bucket, kPolicy);
    if (next == ZL_TABLE_NEXT_BUCKET_EMPTY) {
        return NULL;
    }
    for (;;) {
        ZL_ASSERT_NE(next, ZL_TABLE_NEXT_BUCKET_EMPTY);
        if (kPolicy.eqFn(key, bucket)) {
            return bucket;
        }
        if (next == ZL_TABLE_NEXT_CHAIN_EMPTY) {
            return NULL;
        }
        bucket = GenericTable_getChainBucket(table, next, kPolicy);
        next   = *GenericTable_Bucket_next(bucket, kPolicy);
    }
}

ZL_TABLE_INLINE uint32_t
GenericTable_nextCapacity(uint32_t capacity, uint32_t maxCapacity, bool pow2)
{
    ZL_ASSERT_LE(maxCapacity, ZL_TABLE_MAX_CAPACITY);
    uint32_t newCapacity;
    if (capacity == 0) {
        // We go straight to 4 elements to save on reallocating for 1 and 2
        // elements
        newCapacity = 4;
    } else if (capacity >= 512 && !pow2) {
        // capacity>=512 -> capacity * 1.25
        newCapacity = capacity * 5 / 4;
    } else {
        // 0<capacity<512 -> capacity * 2
        newCapacity = capacity * 2;
    }
    if (newCapacity < capacity || newCapacity > maxCapacity) {
        // overflow or just over max
        return maxCapacity;
    }
    return newCapacity;
}

/// @returns true reservation of at least @p minCapacity succeeded
ZL_TABLE_NO_INLINE bool GenericTable_growChain(
        GenericTable* table,
        uint32_t minCapacity,
        size_t bucketSize)
{
    ZL_ASSERT_LE(minCapacity, table->maxCapacity);
    uint32_t newChainCapacity = GenericTable_nextCapacity(
            table->chainCapacity, table->maxCapacity, /* pow2 */ false);
    newChainCapacity = ZL_MAX(newChainCapacity, minCapacity);
    if (table->chainCapacity >= newChainCapacity) {
        return true;
    }

    size_t totalSize;
    if (ZL_overflowMulST(bucketSize, newChainCapacity, &totalSize)) {
        return false;
    }
    uint8_t* newPtr = GenericTable_reallocMem(table, table->chain, totalSize);
    if (newPtr == NULL) {
        return false;
    }

    table->chain         = newPtr;
    table->chainCapacity = newChainCapacity;
    return true;
}

ZL_TABLE_FORCE_INLINE uint32_t GenericTable_reserveChainIndex(
        GenericTable* table,
        GenericTable_Policy const kPolicy)
{
    if (table->chainFreeList != ZL_TABLE_NEXT_CHAIN_EMPTY) {
        uint32_t const chainIndex = table->chainFreeList;
        void* bucket = GenericTable_getChainBucket(table, chainIndex, kPolicy);
        table->chainFreeList = *GenericTable_Bucket_next(bucket, kPolicy);
        ZL_ASSERT_NE(chainIndex, table->chainFreeList);
        return chainIndex;
    }

    uint32_t const chainIndex = table->chainSize;

    if (table->chainSize >= table->chainCapacity) {
        if (!GenericTable_growChain(table, 0, kPolicy.kBucketSize)) {
            return ZL_TABLE_NEXT_CHAIN_EMPTY;
        }
    }

    ZL_ASSERT_LT(table->chainSize, table->chainCapacity);
    ++table->chainSize;
    return chainIndex;
}

/// @returns the number of buckets in the table.
ZL_TABLE_INLINE uint32_t GenericTable_getTableSize(GenericTable const* table)
{
    return table->tableMask == 0 ? 0 : table->tableMask + 1;
}

ZL_TABLE_INLINE void GenericTable_clear(
        GenericTable* table,
        GenericTable_Policy const kPolicy)
{
    uint32_t const tableSize = GenericTable_getTableSize(table);
    for (size_t tableIdx = 0; tableIdx < tableSize; ++tableIdx) {
        void* const bucket = table->table + tableIdx * kPolicy.kBucketSize;
        *GenericTable_Bucket_next(bucket, kPolicy) = ZL_TABLE_NEXT_BUCKET_EMPTY;
    }
    table->tableSize     = 0;
    table->chainSize     = 0;
    table->chainFreeList = ZL_TABLE_NEXT_CHAIN_EMPTY;
}

/**
 * At this point @p newTable contains the existing hash table in [0, tableSize),
 * because it has been realloced.
 */
ZL_TABLE_FORCE_INLINE void GenericTable_rehash(
        GenericTable* table,
        uint8_t* newTable,
        uint32_t newTableMask,
        GenericTable_Policy const kPolicy)
{
    uint32_t const tableSize    = GenericTable_getTableSize(table);
    uint32_t const newTableSize = newTableMask + 1;

    // Set the new buckets in [tableSize, newTableSize) to be empty
    for (size_t tableIdx = tableSize; tableIdx < newTableSize; ++tableIdx) {
        void* const bucket = newTable + tableIdx * kPolicy.kBucketSize;
        *GenericTable_Bucket_next(bucket, kPolicy) = ZL_TABLE_NEXT_BUCKET_EMPTY;
    }

    for (uint32_t tableIdx = 0; tableIdx < tableSize; ++tableIdx) {
        void* const inlineBucket = newTable + tableIdx * kPolicy.kBucketSize;
        uint32_t next = *GenericTable_Bucket_next(inlineBucket, kPolicy);

        // If the bucket is empty, nothing to do
        if (next == ZL_TABLE_NEXT_BUCKET_EMPTY) {
            continue;
        }

        // Move the inline bucket into the chain
        uint32_t chainIndex = GenericTable_reserveChainIndex(table, kPolicy);
        ZL_ASSERT_NE(
                chainIndex,
                ZL_TABLE_NEXT_CHAIN_EMPTY,
                "reserve() guarantees there is at least one extra entry in the chain");
        void* bucket = GenericTable_getChainBucket(table, chainIndex, kPolicy);
        memcpy(bucket, inlineBucket, kPolicy.kBucketSize);

        // Clear the inline bucket
        *GenericTable_Bucket_next(inlineBucket, kPolicy) =
                ZL_TABLE_NEXT_BUCKET_EMPTY;

        // bucket: The current bucket we're processing. Always in the chain.
        // next: Copy of `bucket.next`.
        for (;;) {
            size_t const hash = kPolicy.hashFn(bucket);
            ZL_ASSERT_EQ((hash & table->tableMask), tableIdx);
            size_t const newTableIdx = hash & newTableMask;
            ZL_ASSERT(
                    (newTableIdx & newTableMask) == tableIdx
                    || newTableIdx == (tableSize + tableIdx));

            // Move this bucket to the new position.
            void* newBucket = newTable + newTableIdx * kPolicy.kBucketSize;
            uint32_t* const newNext =
                    GenericTable_Bucket_next(newBucket, kPolicy);

            if (*newNext == ZL_TABLE_NEXT_BUCKET_EMPTY) {
                // Copy into inline bucket
                memcpy(newBucket, bucket, kPolicy.kBucketSize);
                *newNext = ZL_TABLE_NEXT_CHAIN_EMPTY;
                // Push the chain bucket into the free list
                *GenericTable_Bucket_next(bucket, kPolicy) =
                        table->chainFreeList;
                ZL_ASSERT_NE(chainIndex, table->chainFreeList);
                table->chainFreeList = chainIndex;
            } else {
                ZL_ASSERT_NE(chainIndex, ZL_TABLE_NEXT_CHAIN_EMPTY);
                *GenericTable_Bucket_next(bucket, kPolicy) = *newNext;
                *newNext                                   = chainIndex;
            }

            ZL_ASSERT_NE(next, ZL_TABLE_NEXT_BUCKET_EMPTY);
            if (next == ZL_TABLE_NEXT_CHAIN_EMPTY) {
                break;
            }

            chainIndex = next;
            bucket     = GenericTable_getChainBucket(table, next, kPolicy);
            next       = *GenericTable_Bucket_next(bucket, kPolicy);
        }
    }
}

ZL_TABLE_FORCE_INLINE bool GenericTable_reserve(
        GenericTable* table,
        uint32_t capacity,
        bool guaranteeNoAllocations,
        GenericTable_Policy const kPolicy)
{
    ZL_ASSERT_LE(table->maxCapacity, ZL_TABLE_MAX_CAPACITY);
    if (capacity <= table->tableCapacity) {
        return true;
    }
    if (capacity > table->maxCapacity) {
        return false;
    }

    // Ensure the chain table has space for at least one entry.
    // This property is needed by rehash, but it should be done before
    // reallocing the table, so that if it fails the state of the table
    // is not modified.
    if (table->chainFreeList == ZL_TABLE_NEXT_CHAIN_EMPTY
        && table->chainSize >= table->chainCapacity) {
        if (!GenericTable_growChain(table, 0, kPolicy.kBucketSize)) {
            return false;
        }
        ZL_ASSERT_LT(table->chainSize, table->chainCapacity);
    }

    uint32_t const curTableSize = GenericTable_getTableSize(table);
    ZL_ASSERT(ZL_isPow2(curTableSize));
    uint32_t const newCapacity = ZL_MAX(
            capacity,
            GenericTable_nextCapacity(
                    table->tableCapacity, table->maxCapacity, /* pow2 */ true));
    uint32_t const newTableSize = 2 * (1u << ZL_nextPow2(newCapacity));
    ZL_ASSERT_GT(newTableSize, curTableSize);
    size_t totalSize;
    if (ZL_overflowMulST(newTableSize, kPolicy.kBucketSize, &totalSize)) {
        return false;
    }
    uint8_t* newTable = GenericTable_reallocMem(table, table->table, totalSize);
    if (newTable == NULL) {
        return false;
    }

    GenericTable_rehash(table, newTable, newTableSize - 1, kPolicy);

    ZL_ASSERT_NE(newTableSize, 0);
    table->table         = newTable;
    table->tableMask     = newTableSize - 1;
    table->tableCapacity = newCapacity;

    // Unless we want to guarantee no allocations, don't resize the chain.
    // We'll resize it as needed when we hit collisions.
    if (!guaranteeNoAllocations) {
        return true;
    }

    // Ensure the chain is large enough to guarnatee no allocations.
    return GenericTable_growChain(table, capacity, kPolicy.kBucketSize);
}

ZL_TABLE_FORCE_INLINE GenericTable_Insert GenericTable_insert(
        GenericTable* table,
        void const* entry,
        GenericTable_Policy const kPolicy,
        GenericTable_OutlinedReserve const outlinedReserveFn)
{
    ZL_ASSERT_NN(entry);
    ZL_ASSERT_LE(table->tableSize, table->tableCapacity);
    if (ZL_UNLIKELY(table->tableSize == table->tableCapacity)) {
        if (!outlinedReserveFn(table, table->tableSize + 1)) {
            return (GenericTable_Insert){ NULL, false, true };
        }
    }
    void* bucket  = GenericTable_getTableBucket(table, entry, kPolicy);
    uint32_t next = *GenericTable_Bucket_next(bucket, kPolicy);
    if (next == ZL_TABLE_NEXT_BUCKET_EMPTY) {
        memcpy(bucket, entry, kPolicy.kEntrySize);
        *GenericTable_Bucket_next(bucket, kPolicy) = ZL_TABLE_NEXT_CHAIN_EMPTY;
        ++table->tableSize;
        return (GenericTable_Insert){ bucket, true, false };
    }
    uint32_t chainIndex = ZL_TABLE_NEXT_CHAIN_EMPTY;
    for (;;) {
        ZL_ASSERT_NE(next, ZL_TABLE_NEXT_BUCKET_EMPTY);
        if (kPolicy.eqFn(entry, bucket)) {
            return (GenericTable_Insert){ bucket, false, false };
        }
        if (next != ZL_TABLE_NEXT_CHAIN_EMPTY) {
            chainIndex = next;
            bucket = GenericTable_getChainBucket(table, chainIndex, kPolicy);
            next   = *GenericTable_Bucket_next(bucket, kPolicy);
            continue;
        }

        ZL_ASSERT_NULL(GenericTable_find(table, entry, kPolicy));

        uint32_t newChainIndex = GenericTable_reserveChainIndex(table, kPolicy);
        if (newChainIndex == ZL_TABLE_NEXT_CHAIN_EMPTY) {
            return (GenericTable_Insert){ NULL, false, true };
        }

        // We may have re-allocated the chain. If our bucket is in the chain
        // refetch it.
        if (chainIndex != ZL_TABLE_NEXT_CHAIN_EMPTY) {
            bucket = GenericTable_getChainBucket(table, chainIndex, kPolicy);
        }

        *GenericTable_Bucket_next(bucket, kPolicy) = newChainIndex;
        bucket = GenericTable_getChainBucket(table, newChainIndex, kPolicy);
        memcpy(bucket, entry, kPolicy.kEntrySize);
        *GenericTable_Bucket_next(bucket, kPolicy) = ZL_TABLE_NEXT_CHAIN_EMPTY;
        ++table->tableSize;
        return (GenericTable_Insert){ bucket, true, false };
    }
}

ZL_TABLE_FORCE_INLINE bool GenericTable_erase(
        GenericTable* table,
        void const* key,
        GenericTable_Policy const kPolicy)
{
    ZL_ASSERT_NN(key);
    if (table->table == NULL) {
        return false;
    }
    void* bucket  = GenericTable_getTableBucket(table, key, kPolicy);
    uint32_t next = *GenericTable_Bucket_next(bucket, kPolicy);
    if (next == ZL_TABLE_NEXT_BUCKET_EMPTY) {
        return false;
    }
    if (kPolicy.eqFn(key, bucket)) {
        if (next == ZL_TABLE_NEXT_CHAIN_EMPTY) {
            *GenericTable_Bucket_next(bucket, kPolicy) =
                    ZL_TABLE_NEXT_BUCKET_EMPTY;
        } else {
            void* const nextBucket =
                    GenericTable_getChainBucket(table, next, kPolicy);
            memcpy(bucket, nextBucket, kPolicy.kBucketSize);

            *GenericTable_Bucket_next(nextBucket, kPolicy) =
                    table->chainFreeList;
            table->chainFreeList = next;
        }
        --table->tableSize;
        return true;
    }

    for (;;) {
        uint32_t* prev = GenericTable_Bucket_next(bucket, kPolicy);
        if (next == ZL_TABLE_NEXT_CHAIN_EMPTY) {
            return false;
        }
        bucket = GenericTable_getChainBucket(table, next, kPolicy);
        next   = *GenericTable_Bucket_next(bucket, kPolicy);
        ZL_ASSERT_NE(next, ZL_TABLE_NEXT_BUCKET_EMPTY);
        if (kPolicy.eqFn(key, bucket)) {
            ZL_ASSERT_EQ(
                    (char const*)bucket,
                    (char const*)GenericTable_getChainBucket(
                            table, *prev, kPolicy));
            *GenericTable_Bucket_next(bucket, kPolicy) = table->chainFreeList;
            table->chainFreeList                       = *prev;
            *prev                                      = next;
            --table->tableSize;
            return true;
        }
    }
}

ZL_END_C_DECLS

#endif
